package 分治;

public class MaxSubArray {
	public static void main(String[] args) {
		
		System.out.println(new MaxSubArray().maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
	}
	
	public int maxSubArray(int[] array) {
		if (array == null || array.length == 0) return 0;
		return maxSubArray(array, 0, array.length);
	}
	
	/**
	 * 求出[begin, end)之间的最大连续子序列之和
	 * @param begin
	 * @param end
	 * @return
	 */
	private int maxSubArray(int[] array, int begin, int end) {
		if (end - begin < 2) return array[begin];
		int mid = (begin + end) >> 1;
		int max = 0;	// 记录横跨[begin, mid)和[mid, end)的最大连续序列之和
		
		int leftMax = Integer.MIN_VALUE;
		int leftSum = 0;
		for (int i = mid - 1; i >= begin; i--) {
			leftSum += array[i];
			leftMax = Math.max(leftMax, leftSum);
		}
		
		int rightMax = Integer.MIN_VALUE;
		int rightSum = 0;
		for (int i = mid; i < end; i++) {
			rightSum += array[i];
			rightMax = Math.max(rightMax, rightSum);
		}
		max = leftMax + rightMax;
		return Math.max(max, Math.max(maxSubArray(array, begin, mid), maxSubArray(array, mid, end)));
	}
}
